Pedersen Hash
参考資料
Pedersenハッシュ関数(4-bit window Pedersen hash function)は、ビット列を楕円曲線上の圧縮点に対応付ける安全なハッシュ関数であり、主にゼロ知識証明の演算回路で使用されるこのハッシュ関数を標準化することを目的とし、その他にもマークル木や安全なハッシュ関数を必要とするあらゆるユースケースで汎用的に使用できるようにするものである。
標準化の一環として、ハッシュ関数に用いる楕円曲線、与えられたビット列からPedersenハッシュを計算するプロセス、ゼロ知識証明で利用可能な演算回路を用いたビット列からのハッシュ計算について詳述している。
スポンジ構造などを持たない？
Motivation
Pedersenハッシュ関数の第一の利点は、その効率性である。ハッシュを効率的に計算できるため、zk-SNARK証明に関連する回路で使用するための魅力的な提案である
Background
Pedersenハッシュはすでに定義されており、ZCashチームによって最新のネットワークアップグレードであるSaplingで使用されている（Hopwood et al.）彼らは、Jubjub楕円曲線と3ビットルックアップテーブルを使用して、このハッシュを構築している。この文書では、Baby-Jubjub楕円曲線と4ビット窓を用いたPedersenハッシュ関数の別の実装を提案し、3ビット窓を用いるよりもビットあたりの制約が少なくてすむことを示す。 Baby-Jubjub楕円曲線
Pedersen Hash
$ P_0...P_kを$ G = { P ∈ E(F_p) | rP = O }から入手する
この時、いずれの点も関係が導けないようにする必要があり、D = "string seed" に従う、H = Keccak256(D || S) が楕円曲線 E の点になる最小の数を保持するバイト S を使用する。
入力メッセージMを最大 200 ビットのシーケンスに分割し、それぞれを 4 ビットのチャンクに分割する。
M が 4 の倍数でない場合、0 ビットを追加して M を 4 の倍数にパディングするが、これは衝突性を高めてしまう。
つまり、4×50のmが生まれ、それが$ l個存在する
これを以下のように暗号化する。
$ enc(m_j) = (2b_3 − 1) · (1 + b_0 + 2b_1 + 4b_2)
$ ⟨𝑀_𝑖⟩=∑_{𝑗=0}^{𝑘_{𝑖−}1}𝑒𝑛𝑐(𝑚_𝑗)⋅2^{5_𝑗}
この時、ハッシュ関数HへMを入力すると
$ H(M) = <M_0> · P_0 + <M_1> · P_1 + <M_2> · P_2 + · · · + <M_l> · P_l
上記の式は G の要素の線形結合であるため、それ自体もG の要素。つまり、結果の Pedersen ハッシュ H(M) は、楕円曲線の点
Pedersen Hashを計算するために使用する回路
https://scrapbox.io/files/63ce671ad36a42001e372046.png
https://scrapbox.io/files/63ce5f79dc7e5a001d9f9334.png
ジェネレータのセットは固定されているので、その倍数をあらかじめ計算し、4ビットのルックアップウィンドウを使って正しいポイントを選択することができる。
pがランダムな理由？
これはセレクタと呼ばれる回路に示されるように行われる。この回路は4ビットのチャンク入力を受け、点を返す。
最初の3ビットは点の正しい倍数を選択するために使用され、最後のビットは点の符号を決定します。
符号はx座標を正とするか負とするかを決めるもので、Edwards曲線と同様に、点を否定することはその最初の座標を否定することに相当する。